//
// Created by ASUS on 2023/9/20.
//
/*
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：
输入：n = 13
输出：6

示例 2：
输入：n = 0
输出：0

提示：0 <= n <= 10^9
 */
#include <bits/stdc++.h>
using namespace std;

int countDigitOne(int n) {
	auto s = to_string(n);//把数字转换成字符串
	int m = s.length(), dp[m][m];
	memset(dp, -1, sizeof(dp));
	function<int(int, int, bool)> f = [&](int i, int cnt1, bool is_limit) -> int {
		if (i == m) return cnt1;//枚举超了最后一位直接返回当前数组1的个数
		if (!is_limit && dp[i][cnt1] >= 0) return dp[i][cnt1];//如果没被限制而且已经计算过
		int res = 0;
		for (int d = 0, up = is_limit ? s[i] - '0' : 9; d <= up; ++d) // 枚举第i位要填入的数字 d
			res += f(i + 1, cnt1 + (d == 1), is_limit && d == up);//枚举下一位
		if (!is_limit) dp[i][cnt1] = res;
		return res;
	};
	return f(0, 0, true);
}